#pragma once
#include <iostream>

using namespace std;

template<class T>
class QueueNode
{
public:
	T data;
	QueueNode* next;
	QueueNode(T x = 0 ):data(x),next(nullptr)
	{}
};
template<class T>
class Queue
{
public:
	Queue()
		:head(nullptr),
		tail(nullptr),
		size(0)
	{}
	void push(T x)
	{
		QueueNode<T>* node = new QueueNode<T>(x);
		if (head == nullptr)
		{
			head = tail = node;
		}
		else
		{
			tail->next = node;
			tail = node;
		}
		size++;
	}
	void pop()
	{
		if (size == 1)
		{
			delete(head);
			head = tail = nullptr;
		}
		else
		{
			auto node = head->next;
			delete(head);
			head = node;
		}
		size--;
	}
	T front()
	{
		if (head)
		{
			return head->data;
		}
	}
	T  back()
	{
		if (tail)
		{
			return tail->data;
		}
	}
	bool empty()
	{
		return size == 0;
	}
	int Size()
	{
		return size;
	}
	void Print()
	{
		while (!empty())
		{
			T data = front();
			pop();
			printf("%d->", data);
		}
	}
	~Queue()
	{
		delete(head);
		delete(tail);
	}
private:
	QueueNode<T>* head;
	QueueNode<T>* tail;
	int size;
};